package problems.contest;

import utils.beans.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 第 320 场周赛
 * <p>https://leetcode.cn/contest/weekly-contest-320/</p>
 *
 * @author habitplus
 * @since 20:09, 2022/11/22
 */
public class WCT320 {

    /**
     * T1|2475. 数组中不等三元组的数目
     * <p>https://leetcode.cn/problems/number-of-unequal-triplets-in-array/</p>
     */
    public int unequalTriplets(int[] nums) {
        int n = nums.length;
        int ret = 0;

        // 枚举 i
        for (int i = 0; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) {
                        ++ret;
                    }
                }
            }

        }

        return ret;
    }

    /**
     * T2|2476. 二叉搜索树最近节点查询
     * <p>https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/</p>
     */
    private List<Integer> data = new ArrayList<>();
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        dfs(root);

        if (data.size() < 1) return null;

        List<List<Integer>> ret = new ArrayList<>();
        int k, val;

        for (int q : queries) {
//            min = searchMin(q);
            k = searchMax(q);

            List<Integer> tmp = new ArrayList<>();
            val = data.get(k);
            if (val == q) {
                tmp.add(val);
                tmp.add(val);
            } else if (val > q){
                // 找到了 >= q 的最小值
                tmp.add(k > 0 ? data.get(k - 1) : -1);
                tmp.add(val);
            } else {
                // 找到了 <= q 的最大值
                tmp.add(val);
                tmp.add (k == data.size() - 1 ? -1 : data.get(k + 1));
            }
            ret.add(tmp);
        }

        return ret;
    }

    // 搜索 <= target 的最大值
    private int searchMax(int target) {

        int l = 0;
        int r = data.size() - 1;
        int m;

        while (l < r) {
            m = l + r / 2;
            if (data.get(m) > target) r = m - 1;
            else if (data.get(m) == target) return m;
            else l = m + 1;
        }

        return l;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;

        dfs(root.left);
        data.add(root.val);
        dfs(root.right);
    }
}
